class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if(0 == len || 0 == k) {
            return new int[0];
        }
        if(1 == k) {
            return nums;
        }
        int[] ret = new int[len - k + 1];
        //双端队列
        Deque<Integer> deque = new LinkedList<>();
        int i = 0;
        deque.push(nums[0]);
        //第一个窗口(构建窗口)
        for(i = 1;i<k;i++) {
            while(!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
        }
        int j = 0;
        ret[j++] = deque.peekFirst();
        for(;i<len;i++) {
            //如果队列中第一个数为滑动窗口开头应该删除的数字,就删除
            if(deque.peekFirst() == nums[i-k]){
                deque.removeFirst();
            }
            while(!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);
            ret[j++] = deque.peekFirst();
        }
        return ret;

    }
}